//
// Created by dxyinme on 2021/10/6.
//

#ifndef VSORT_V_SORT_ARRAY_H
#define VSORT_V_SORT_ARRAY_H

#include "thread_pool.h"
#include <algorithm>

namespace Vsort {

std::vector<std::tuple<size_t, size_t>> Divide(size_t partSize, size_t len);

template<typename T, typename Compare>
void SortArrayExThread(
        T* arr,
        size_t len,
        ThreadPool* thPool,
        Compare cmp);

template<typename T, typename Compare>
void MergeArray(
        T* arr,
        size_t l,
        size_t m,
        size_t r,
        Compare cmp);

}

template<typename T, typename Compare>
void Vsort::SortArrayExThread(
        T* arr,
        size_t len,
        ThreadPool* thPool,
        Compare cmp) {
  size_t workersNum = thPool->GetWorkersNum();
  size_t partSize = len / workersNum + 1;
  auto parts = Divide(partSize, len);
  std::vector<std::future<void>> tasks;
  for (auto part : parts) {
    tasks.emplace_back(thPool->enqueue([&arr, cmp, part] {
      std::sort(arr + std::get<0>(part), arr + std::get<1>(part), cmp);
    }));
  }
  for (auto&& task : tasks) task.get();
  while (parts.size() > 1) {
    std::vector<std::tuple<size_t, size_t>> tmp;
    std::vector<std::future<void>> mergeTasks;
    for (size_t i = 0; i < parts.size(); i += 2) {
      if (i + 1 >= parts.size()) {
        tmp.emplace_back(parts[i]);
      } else {
        mergeTasks.emplace_back(thPool->enqueue([&arr, cmp] (size_t l, size_t m, size_t r) {
          MergeArray<T, Compare>(
                  arr,
                  l, m, r,
                  cmp);
        },std::get<0>(parts[i]), std::get<1>(parts[i]), std::get<1>(parts[i + 1])));
        tmp.emplace_back(std::get<0>(parts[i]),
                         std::get<1>(parts[i + 1]));
      }
    }
    for (auto&& task : mergeTasks) task.get();
    parts.assign(tmp.begin(), tmp.end());
  }
}


template<typename T, typename Compare>
void Vsort::MergeArray(
        T* arr,
        size_t l,
        size_t m,
        size_t r,
        Compare cmp) {
  T* tmpArr = new T[r - l];
  size_t t1 = l, t2 = m, t_tmp = 0;
  while (t1 < m && t2 < r) {
    if (cmp(*(arr+t1), *(arr+t2))) {
      tmpArr[t_tmp++] = arr[t1++];
    } else {
      tmpArr[t_tmp++] = arr[t2++];
    }
  }
  while (t1 < m) tmpArr[t_tmp++] = arr[t1++];
  while (t2 < r) tmpArr[t_tmp++] = arr[t2++];
  for (size_t i = 0; i < r - l; i ++) {
    arr[i + l] = tmpArr[i];
  }
  delete[] tmpArr;
}

#endif //VSORT_V_SORT_ARRAY_H
